package leetcode;

//Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.
//For example,
//Given:
//s1 ="aabcc",
//s2 ="dbbca",
//When s3 ="aadbbcbcac", return true.
//When s3 ="aadbbbaccc", return false.
public class InterleavingString {

	public static void main(String[] args) {
//		System.out.println(isInterleave2("", "", "a"));
		String s1 = "aabc";
		String s2 = "abad";
		String s3 = "aabadabc";
		InterleavingString object = new InterleavingString();
		System.out.println(object.isInterleave3(s1, s2, s3));
	}
	
	
	//比如 aa,ab ,aaba   如果是按照curIndicator（初始为1）中判断相等 那么就会判断成a ab aba ---> ab  ba,就是false 
	//同样 如果是始终判定首先匹配第一个字符串  s1 ="aabcc",s2 ="dbbca", s3 ="aadbbcbcac"
	//那么就会到达cc  bca  cbcac --> c ca  cac  -->  ca ac
	
 	//思路错了，你根本就无法判断下一个字母是去找s1的还是s2的
	//所以这道题要用动态规划的思想来解决，也就是说只去掉其中一个的（匹配s1的，匹配s2的）然后将两者的结果相或
	public static boolean isInterleave1(String s1, String s2, String s3){
		if(s3 == null || s3.length() != s1.length() + s2.length()){
			return false;
		}
		int point1 = 0;  //用于指向s1中字符的位置
		int point2 = 0;  //用于指向s2中字符的位置
		int curIndicator = 1;
		char[] string1 = s1.toCharArray();
		char[] string2 = s2.toCharArray();
		char[] string3 = s3.toCharArray();
		for (int i = 0; i < string3.length; i++) {
			System.out.println("point1  " + point1 + " point2  " + point2 + " " + string3[i]);
			if (curIndicator == 1) {
				if (point1 < string1.length && string3[i] == string1[point1]) {
					point1++;
					curIndicator = 1;
				} else if (point2 < string2.length
						&& string3[i] == string2[point2]) {
					point2++;
					curIndicator = 2;
				} else {
					return false;
				}
			}else {
				if (point2 < string2.length && string3[i] == string2[point2]) {
					point2++;
					curIndicator = 2;
				} else if (point1 < string1.length
						&& string3[i] == string1[point1]) {
					point1++;
					curIndicator = 1;
				} else {
					return false;
				}
			}
		}
		return true;
	}
	
	public static boolean isInterleave(String s1, String s2, String s3){
		if(s3 == null || s1 == null || s2 == null || s3.length() != s1.length() + s2.length()){
			return false;
		}
		boolean[][][] result = new boolean[s1.length() + 1][s2.length() + 1][s3.length() + 1];
		int point1 = 0;  //用于指向s1中字符的位置
		int point2 = 0;  //用于指向s2中字符的位置
		int position = 0;
		char[] string1 = s1.toCharArray();
		char[] string2 = s2.toCharArray();
		char[] string3 = s3.toCharArray();
		result[0][0][0] = true;
		for (int i = 1; i < string1.length; i++) {
			for (int j = 1; j < string3.length; j++) {
				result[i][0][j] = false;
			}
		}
		for (int i = 1; i < string2.length; i++) {
			for (int j = 1; j < string3.length; j++) {
				result[0][i][j] = false;
			}
		}
		for (int k = 1; k < string3.length; k++) {
			for (int j = 1; j <= string2.length; j++) {
				for (int i = 1; i <= string1.length; i++) {
					System.out.println("[" + i + "][" + j+ "][" + k +"]" + result[i][j][k]);
					if(k == 1){
						result[i][j][k] = string3[string3.length - k] == string1[string1.length - i]
								|| string3[string3.length - k] == string2[string1.length - j];
						System.out.println("[" + i + "][" + j+ "][" + k +"]" + result[i][j][k]);
						continue;
					}
					if (string3[string3.length - k] == string1[string1.length - i]
							|| string3[string3.length - k] == string2[string2.length - 1]) {
						result[i][j][k] = result[i - 1][j][k - 1] || result[i][j - 1][k - 1];
					}else {
						result[i][j][k] = false;
					}
//					else if(string1[i - 1] == string3[k]){
//						result[i][j][k] = false;
//						result[i][j][k] = result[i - 1][j][k - 1] ;
//					}else if(string3[k] == string2[j - 1]){
//						result[i][j][k] = result[i][j - 1][k - 1] ;
//					}
//					else{
//						return false;
//					}
				}
//				if(position == string3.length - 1){
//					result[i][j] = string3[position] == string1[i]
//							|| string3[position] == string2[j];
//				}
//				if (string3[position] == string1[i]
//						&& string3[position] == string2[j]) {
//					position++;
//					result[i][j] = result[i - 1][j] || result[i][j - 1];
//				}else if(string1[i] == string3[position]){
//					position++;
//					result[i][j] = result[i - 1][j];
//				}else if(string3[position] == string2[j]){
//					position++;
//					result[i][j] = result[i][j - 1];
//				}else{
//					return false;
//				}
			}
		}
		return true;
	}
	
	//运行时间：48ms
	//占用内存：755k
	// result[i][j] = string3[i + j] == string1[i] && result[i + 1][j]
	// || string3[i + j] == string2[j] && result[i][j + 1];
	// 也就是说如果与两个字符串中的i 、j都相等那么就等于两者结果的或，如果只与一个相等，那么就等于那个结果
	// 比如下面的例子
	// aa ab aaba --->  a ab aba 与  aa b aba相或  。 aa b aba  就只等于 a b ba
	public static boolean isInterleave2(String s1, String s2, String s3){
		System.out.println(s1.length() + " " + s2.length() + s3.length());
		if(s3 == null || s1 == null || s2 == null || s3.length() != s1.length() + s2.length()){
			return false;
		}
		//result[i][j]表示以string[i ... length - 1]与string2[j ... length - 1]是否与string[3]中两者的长度相匹配
		boolean[][] result = new boolean[s1.length() + 1][s2.length() + 1];
		char[] string1 = s1.toCharArray();
		char[] string2 = s2.toCharArray();
		char[] string3 = s3.toCharArray();
		result[string1.length][string2.length] = true;
		//初始化边界条件
		//当且仅当两者字母相同的时候并且前面的结果为true 才为true
		for (int j = string2.length - 1; j >= 0; j--) {
			result[string1.length][j] = result[string1.length][j + 1] && string2[j] == string3[s1.length() + j];
		}
		for (int i = string1.length - 1; i >= 0; i--) {
			result[i][string2.length] = result[i + 1][string2.length] && string1[i] == string3[s2.length() + i];
		}
		for (int j = string2.length - 1; j >= 0; j--) {
			for (int i = string1.length - 1; i >= 0; i--) {
				result[i][j] = string3[i + j] == string1[i] && result[i + 1][j]
						|| string3[i + j] == string2[j] && result[i][j + 1];
			}
		}
		for (int i = 0; i <= string1.length; i++) {
			for (int j = 0; j <= string2.length; j++) {
				System.out.print(result[i][j] + "  ");
			}
			System.out.println();
		}
		return result[0][0];
	}
	
	
	//15ms, beat 8.62%
	//but I personally think about the idea
    public boolean isInterleave3(String s1, String s2, String s3) {
        if(s1 == null || s2 == null || s3 == null){
        	return true;
        }
        int length1 = s1.length();
        int length2 = s2.length();
        int length3 = s3.length();
        if(length1 + length2 != length3){
        	return false;
        }
        
        //dp[i][j] 表示s1[0...i - 1]和s2[0...j - 1]是否可以交错组成s3[0...i + j - 1]
        //dp[i][j] = dp[i - 1][j] || dp[i][j - 1]; if(s1[i - 1] == s3[i + j - 1] && s2[j - 1] == s3[i + j - 1])
        //dp[i][j] = dp[i - 1][j]  if (s1[i - 1] == s3[i + j - 1])
        //dp[i][j] = dp[i][j - 1] if(s2[j - 1] == s3[i + j - 1])
        //dp[i][j] = false; if above is all false;
        boolean[][] dp = new boolean[length1 + 1][length2 + 1];
        dp[0][0] = true;
        for(int i = 1; i <= length1; i++){
        	dp[i][0] = s1.substring(0, i).equals(s3.substring(0, i));
        }
        for(int j = 1; j <= length2; j++){
        	dp[0][j] = s2.substring(0, j).equals(s3.substring(0, j));
        }
        
        for(int i = 1; i <= length1; i++){
        	for(int j = 1; j <= length2; j++){
        		if(s1.charAt(i - 1) == s3.charAt(i + j - 1)
        				&& s1.charAt(i - 1) == s3.charAt(i + j - 1)){
        			dp[i][j] = dp[i - 1][j] || dp[i][j - 1];
        		}else if(s1.charAt(i - 1) == s3.charAt(i + j - 1)){
        			dp[i][j] = dp[i - 1][j];
        		}else if(s2.charAt(j - 1) == s3.charAt(i + j - 1)){
        			dp[i][j] = dp[i][j - 1];
        		}else{
        			dp[i][j] = false;
        		}
            }
        }
        
        for(int i = 0; i <= length1; i++){
        	for (int j = 0; j <= length2; j++) {
				System.out.print(dp[i][j] + "  ");
			}
        	System.out.println();
        }
        return dp[length1][length2];
    }
    
}
